package sort.insertsort;

/**
 * 插入排序
 *
 * 参考： https://blog.csdn.net/qq_43794633/article/details/121612149
 *
 * 算法步驟
 *
 * 首先从第一个元素开始，该元素被认为是有序的；
 * 取出下一个元素，在已经排序的元素序列中从后往前进行扫描；
 * 如果该已排好序的元素大于新元素，则将该元素移到下一位置；
 * 重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；
 * 将新元素插入到该位置后；
 * 重复步骤2~5。
 *
 * @author xushijian
 * @date 2021/12/15 10:24
 */
public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {1, 7, 2, 8, 10, 1, 9, 0};

        insertSort(arr);

        System.out.println("insert sort result is :");
        for (int i : arr) {
            System.out.println(i);
        }

    }

    /**
     * 插入排序（后一个与前一个比较）
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {

        if (arr == null || arr.length <= 1) {
            return;
        }
        int len = arr.length;
        int n;
        int next;
        for (int i = 0; i < len - 1; i++) {
            n = i;
            next = arr[i + 1];
            while (n >= 0) {
                //如果next 小于 上一个节点，则交换
                if (next < arr[n]) {
                    arr[n + 1] = arr[n];
                    arr[n] = next;
                }
                n--;
            }
        }
    }

}